package org.xingole.leetcode.dp;

/**
 * <a href="https://leetcode.com/problems/non-negative-integers-without-consecutive-ones/description/">
 * Problem Description</a>
 */
public class NonNegativeIntegersWithoutConsecutiveOnes {
    /**
     * 
     * @param n a positive integer
     * @return the number of the integers in the range [0, n] whose binary representation
     * do not contain consecutive ones.
     */
    public int findIntegers(int n) {
        int[] dp = new int[31];
        dp[0] = dp[1] = 1;
        for (int h = 2; h < 31; ++h) {
            dp[h] = dp[h - 1] + dp[h - 2];
        }

        int pre = 0;
        int res = 0;
        for (int shift = 29; shift >= 0; --shift) {
            int mask = 1 << shift;
            if ( ( n & mask ) != 0 ) {
                res += dp[shift + 1];
                if (pre == 1) {
                    break;
                }
                pre = 1;
            } else {
                pre = 0;
            }
            
            if (shift == 0) {
                ++res;
            }
        }

        return res;
    }

    /**
     * Complexity Analysis
     * 
     * <ul>
     *      <li>Time complexity: O(32*n). We test the 32 consecutive positions of every
     * number from 0 to n. Here, n refers to given number.
     *      <li>Space complexity: O(1). Constant space is used.
     * </ul>
     */
    public int findIntegers0(int n) {
        /*
         * Approach 1: Brute Force
         * 
         * We can tranverse through all the numbers from 1 to num. For every current
         * number chosen, we can check all the consecutive positions in this number
         * to check if the number contains two consecutive ones or not. If not, we
         * increment the count of the resultant numbers with no consecutive ones.
         * 
         */
        int count = 0;
        for (int i = 0; i <= n; i++) {
            if (check(i)) {
                count++;
            }
        }

        return count;
    }

    private boolean check(int n) {
        /*
         * To check if a 1 exists at the position x (counting from the LSB side), in the
         * current number n, we can proceed as follows. We can shift a binary 1
         * x-1 times towards the left to get a number y which has a 1 only at the xth
         * position. Now, logical ANDing of n and y will result in a logical 1 output
         * only if n contains 1 at the xth position.
         */
        int i = 31;
        while (i > 0) {
            if ( ( n & ( 1 << i ) ) != 0 && 
                 ( n & ( 1 << ( i - 1 ) ) ) != 0
            ) {
                return false;
            }
            i--;
        }

        return true;
    }
}
